package hot

/*
原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:
输入: prices = [1]
输出: 0

思路: 动态规划

一. dp数组含义
dp[i][j] 表示第i天, 状态为j, 所持有的现金数

可以区分出四个状态:
状态0: 持有股票状态(今天买入股票, 或者是之前就买入了股票, 然后没有操作, 一直持有)
不持有股票, 这里就有两种卖出股票状态

	状态1: 保持卖出股票的状态(两天钱就卖出了股票, 度过一天冷冻期. 或者是前一天就是卖出股票状态, 一直没操作)
	状态2: 今天卖出股票
	状态3: 今天为冷冻期状态, 但冷冻期状态不可持续, 只有一天!

之前题目, 今天卖出股票, 为什么没有单独列出来呢?
本题有冷冻期, 而冷冻期的前一天, 只能是[今天卖出股票]状态, 如果是[不持有股票状态]那么就很模糊, 因为不一定是卖出股票的操作.

注意这里的每一个状态,
例如状态一, 是持有股票状态,并不一定今天就一定买入股票, 而是说保持买入股票的状态
即: 可能是前几天买的, 之后一直没操作, 所以保持买入股票的状态

二. 递推公式

	达到买入股票状态(状态一) 即: dp[i][0], 有两个具体操作:
		操作一: 前一天就是持有股票状态(状态0), dp[i][0] = dp[i-1][0]
		操作二: 今天买入了, 两种情况
			前一天是冷冻期(状态3), dp[i-1][3]-prices[i]
			前一天是保持卖出股票的状态(状态2), dp[i-1][1]-prices[i]

	达到保持卖出股票状态(状态1) 即: dp[i-1][1], 有两个具体操作:
		操作一: 前一天就是状态1
		操作二: 前一天是冷冻期(状态3)
		即: dp[i][1] = max(dp[i-1][1], dp[i-1][3])

	达到今天就卖出股票状态(状态2) 即: dp[i][2],只有一个操作:
		昨天一定是持有股票状态(状态0), 今天卖出
		即: dp[i][2] = dp[i-1][0] + prices[i]

	达到冷冻期状态(状态3) 即: dp[i][3], 只有一个操作:
		昨天卖出了股票(状态2)
		即: dp[i][3] = dp[i-1][2]

综上所述, 递推公式如下:

	dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]-prices[i]))
	dp[i][1] = max(dp[i-1][1], dp[i-1][3])
	dp[i][2] = dp[i-1][0] + prices[i]
	dp[i][3] = dp[i-1][2]

三. 初始化

	对第0天的4种状态进行赋值
	dp[0][0] = 0
	dp[0][1] = 0
	dp[0][2] = 0
	dp[0][3] = 0

四. 确定遍历顺序

	从递归公式上看, dp[i]依赖于dp[i-1], 所以是从前向后遍历

五. 打印dp数组
*/
func maxProfit(prices []int) int {

	//获取数组长度
	n := len(prices)
	if n < 2 {
		return 0
	}

	//声明dp数组
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, 4)
	}

	//第0天, 持有股票的状态, 肯定是买了第0天的股票, 所以持有现金为-prices[i]
	dp[0][0] = -prices[0]

	//填充dp数组
	//dp[i][0]: 第i天持有股票状态, 所持有的现金数
	//dp[i][1]:
	for i := 1; i < n; i++ {
		//第i天持有股票的状态: max(i-1天就持有了, i-1天卖出的.今天刚买的, i-1天是冷冻期.今天刚买的)
		dp[i][0] = max(dp[i-1][0], max(dp[i-1][1]-prices[i], dp[i-1][3]-prices[i]))
		//第i天保持卖出股票的状态: max(i-1天就保持卖出了, i-1天是冷冻日.今天肯定是保持卖出状态)
		dp[i][1] = max(dp[i-1][1], dp[i-1][3])
		//第i天进行卖出股票的动作: 前一天持有股票的状态 + 今天的股票价格
		dp[i][2] = dp[i-1][0] + prices[i]
		//第i天是冷冻期: 前一天进行卖出动作时持有的现金
		dp[i][3] = dp[i-1][2]
	}

	//返回 max(第i天保持卖出股票的状态, 第i天进行卖出股票的动作, 第i天是冷冻期)
	return max(dp[n-1][1], max(dp[n-1][2], dp[n-1][3]))
}
